COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	AUTOMATIC PROGRAMMING
C00018 ENDMK
C⊗;
AUTOMATIC PROGRAMMING
This file exhibits trouble with lines that end with periods both before
justifying and after. Some lines with internal periods that ended a line
before justification end up too long while lines ending with periods after
justification are too short.


Both a theoretical knowledge of programs and a practical understanding of the
programming process are fundamental to computer science.  The economic importance
of automating computer programming as much as possible is considerable.
Research in automatic programming can be viewed as a logical extension of work
such as that
on assemblers, compilers, very high-level languages, and other aids to programming
such as operating systems, editors, debuggers, and spelling checkers.


Automatic Selection of Data Structures

A system has  been developed which,  given an algorithm  expressed in
terms  of  high-level information  structures such  as  sets, ordered
sets, and relations, automatically chooses efficient  representations
and  produces   a  new  program  that   uses  these  representations [
Representations  are picked  from a  fixed library of  low-level data
structures including linked lists, binary trees, and hash tables.  The
representations  are chosen by  attempting to minimize  the predicted
space-time integral of  the user's program  execution.

Predictions are  based upon  statistics  of  information-structure  use  provided
directly  by the user and  collected by monitoring  executions of the
user  program  using  default  representations  for  the   high-level
structures.  In performance tests this system has exhibited behavior
superior to that of human programmers and is at the stage where it could
be implemented in a very high-level language like SAIL.
This work is reported in Jim Low's thesis [6].


Program-understanding Systems

Progress has also been made in the design of systems which can be said
to have some "program understanding" ability.
The primary evidence
for such ability lies in the capability to synthesize programs, either
automatically or semi-automatically, but such a capability alone
is insufficient
for understanding: the line of reasoning which the system follows during
the synthesis process must also support the claim of "understanding".
We feel that most of our systems behave well in this regard.

The earliest work in this area is reported in [1].
One experimental system used its knowledge
base of "programming facts" to synthesize (among others) programs
which interchange elements, perform a non-recursive sort of three elements,
and find the integer square root, basing choices at decision points
on user responses to questions posed by the system [1, Section 4.4].
Another experimental system can synthesize programs from example
input/output pairs and has written about 20 simple list-processing
functions [5].

These experiments have led us 
to a view that among the major research problems in program
understanding are the exploration of various methods
of program specification, the codification of programming knowledge,
the representation of programming and domain-specific knowledge in
complex programming-understanding systems, and the question of system
organizations for such systems.

Looking at the two experimental systems mentioned above, we see two
different methods of specifying the desired program:  example input/output
pairs and user responses to questions from the system.
There seem to be many other ways in which the desired program
could be specified, ranging from very formal to very informal.
A unifying paradigm would seem to be
a kind of dialog between the user and the system.
In such a dialog any of these methods (or even several of them)
might be employed,
depending on suitability for the program, and preferences of the user.
Work
is currently progressing on various methods of modeling and conducting
such dialogs.

Robert Elschlager is studying natural-language descriptions of programs in
order to develop an appropriate internal representation for them.  From this
has come a representation which is primarily relational, but also has
qualification and quantification primitives.  Possible inputs into this
system might be either a limited subset of English or a more rigidly structured
"parenthesized" English.  Future work includes relating this internal
representation of a program to the programming concepts and data structures it
will use.

Our experimental systems and numerous hand simulations of program-
understanding systems indicate that satisfactory behavior can only
be expected when the system contains a large body of
knowledge.  For the understanding of programs in a given domain, there
is considerable domain-specific knowledge.
Additionally, there seems
to be a large body of "pure" programming knowledge which
is relatively domain independent.

C. Cordell Green and David R. Barstow have worked toward
isolating and codifying this knowledge in the domain of sorting.
A system has been developed for testing the representation of this
knowledge for the process of writing simple iterative sorting programs [2].

Douglas B. Lenat has developed the PUP5 system for writing large 
inductive-inference programs [3].  The system is based around a homogeneous
knowledge base of interacting modules called "beings".
The concept of beings will be the basis for a new system designed to do theory
formation in mathematics.  This system will initially be endowed with general
mathematical strategies.  Then, during an assimilation phase, the system will accept
inputs from a human user in order to learn the core definitions of a specific
field of mathematics (e.g., arithmetic, set theory, Boolean algebra).
Finally, in an investigative mode in conjunction
with the user, the system will creatively propose and explore interesting new
relationships in this field.

A group consisting of C. Cordell Green, David R. Barstow, Avra J. Cohn, Elaine
Kant, Brian P. McCune, and Louis I. Steinberg is working on the use of
"natural" user-machine dialogs to facilitate a system for the construction
and modification of a wide range of programs in the domain of concept formation.
This is a large-scale effort which is currently in the preliminary design
phase, but a system composed of an interacting group of "experts" is
envisaged.  Among these experts would be those concerned with controlling the
dialog with the user, modelling the state of the user, making available knowledge
of
concept formation, modelling the program under construction, and converting
the model into a running LISP program.
Much of the knowledge gained in the work by Low on the automatic selection of
data structures and Green and Barstow on the codification of programming
and utilization knowledge and its utilization in the programming process will
be used in this new system.


Bibliography

[1] Green, C. Cordell, Waldinger, Richard J., Barstow, David R., Elschlager, Robert,
Lenat, Douglas B., McCune, Brian P., Shaw, David E., and Steinberg, Louis I.,
"Progress Report on Program-understanding Systems", Memo AIM-240, Report
STAN-CS-74-444, Artificial Intelligence Laboratory, Computer Science Department,
Stanford University, Stanford, California, August 1974.

[2] Green, Cordell, and Barstow, David, "On Knowledge and Program-understanding
Systems", in preparation.

[3] Lenat, Doug, "BEINGS: Representation of Knowledge as Interacting Modules",
in preparation.

[4] Low, James Richard, "Automatic Coding: Choice of Data Structures", Ph.D. thesis,
Memo AIM-242, Report STAN-CS-74-452, Artificial Intelligence Laboratory,
Computer Science Department, Stanford University, Stanford, California,
August 1974.

[5] Shaw, David Elliot, Swartout, William R., and Green, C. Cordell, "Inferring
LISP Programs from Examples", in preparation.